In a caching scheme, it is sometimes appropriate to assume that the addresses to be accessed are somewhat uniformly spread across the range. Also, for any address, it is possible to determine the information sought that is associated with the address, but it typically takes a while to access the information that corresponds to a particular address. Furthermore, it is sometimes appropriate to assume that once a particular address is accessed, it is likely that the address would be accessed again. In such a scenario, the address could represent a destination to which (or from which) a packet (e.g., a data packet) is to be sent (or received) by a network switch and the information sought might be the port of the network to which the packet must be sent (or from which the packet must be obtained) in order to route the packet properly.
Further, in a computer network, the network switch typically includes a plurality of network ports. The network ports may be classified as input ports and output ports. The network switch receives packets from a number of input ports and forwards the packets to a number of output ports. The network switch determines the output port to which the packet is forwarded dependent on a destination address included in the packet received at one of the input ports.
The network ports to which packets are to be forwarded based on a destination address are stored in a forwarding entry in a forwarding table in the network switch. The forwarding table is searched for the forwarding entry associated with a particular destination address or cache line.
In general, it is not feasible to provide an entry in the forwarding table for each possible destination address accessible through the network switch. For example, for a 48 bit Ethernet destination address, that is, a Media Access Control (MAC) address, 248 forwarding entries are required in the forwarding table to store forwarding information for all the possible MAC addresses. Instead, the forwarding table is implemented as a hash table and the number of forwarding entries in the hash table depends on memory resources. A hash function is performed on the destination address to provide a smaller number which is then used to index the hash table. As a result of performing a hash function on the destination address, multiple destination addresses may map to the same index, that is, aliasing may occur.
In the above scenario, it is inefficient to have constantly stalled processing in order to wait for the port to be searched each time when an address is accessed. One way to avoid stalling is to build a simple one-dimensional array that has as many entries as there are possible address values. One could then store the port information for each particular address in the array element that has the same index pointer as the specific address corresponding to the port information stored therein. This way, if one needs to determine the port corresponding to a given address, the address can serve as the index pointer to the array element for the address being accessed.
A problem associated with using the actual address as an index into the array is that the array becomes significantly large as the address range becomes large. Therefore, a large address range requires a huge amount of memory to be allocated to the cache.
An existing approach to reduce the required size of a cache is to use a hashing function to calculate an index in the cache. Although using a hash as an index decreases the amount of memory used, it also introduces problems caused by aliases. Even if the valid flag indicates that the information in the cache line is valid, one cannot be sure that the information pertains to the address being requested or that it pertains instead to an alias of that address. Note that because the likelihood of collisions typically increases as the number of aliases increases, there is a trade-off between cache size and hashing function used. A way to address the problems introduced by churning is to expand the single data cache line associated with a hash into a set of more than one data lines. Such a cache is called an N-way set associative cache, where N is the number of cache lines associated with a single hash. Such an N-way set is sometimes referred to as a bucket. Therefore, by selecting a hash function and the number of lines for each bucket based upon access patterns, a trade-off between size of the cache and the likelihood of a cache miss (and churning caused by the cache miss) can be made when designing an N-way set associative cache.